package medium;

/**
 * 1969. 数组元素的最小非零乘积
 * 创建时间：2024-03-20 08:51
 * 地址：https://leetcode.cn/problems/minimum-non-zero-product-of-the-array-elements/description/?envType=daily-question&envId=2024-03-20
 */
public class 数组元素的最小非零乘积_1969 {
    public static int minNonZeroProduct(int p) {
        long mod = 1000000007;
        long x = binPow(2, p, mod) - 1;
        long y = (long)1 << (p - 1);
        return (int) (binPow(x - 1, y - 1, mod) * x % mod);
    }

    public static long binPow(long a, long b, long m) {
        long res = 1;
        while(b > 0) {
            // 判断最低位是否为1
            if ((b & 1) > 0) {
                res = res * a % m;
            }
            // 平方
            a = a * a % m;
            // 指数做右移
            b >>= 1;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(minNonZeroProduct(3));
        System.out.println(1 << 2);
    }
}
